#include "mergesort.h"

void _mergesort(int* a,int begin,int end,int* tmp)
{
  if(begin >= end) return;

  int mid = (begin+end)/2;
  //递归使子区间有序
  _mergesort(a,begin,mid,tmp);
  _mergesort(a,mid+1,end,tmp);

  int begin1 = begin; int end1 = mid;
  int begin2 = mid+1; int end2 = end;
  int i = begin;

  while(begin1 <= end1 && begin2 <= end2)
  {
    if(a[begin1] > a[begin2])
    {
      tmp[i++] = a[begin1++];
    }
    else 
    {
      tmp[i++] = a[begin2++];
    }
  }

  while(begin1 <= end1)
  {
    tmp[i++] = a[begin1++]; 
  }

  while(begin2 <= end2)
  {
    tmp[i++] = a[begin2++];
  }

  memcpy(a+begin,tmp+begin,sizeof(int)*(end-begin+1));

}

void mergesort(int* a,int n)
{
  int* tmp = (int*)malloc(sizeof(int)*n);
  _mergesort(a,0,n-1,tmp);
  free(tmp);
  tmp = NULL;
}




void mergesortNF(int* a,int n)
{
  int* tmp = (int*)malloc(sizeof(int)*n);
  int rangeN = 1;
  while(rangeN < n)
  {
    for(int i = 0;i<n;i+=2*rangeN)
    {
      int begin1 = i; int end1 = i + rangeN -1;
      int begin2 = i+rangeN; int end2 = i+2*rangeN-1;
      int j = i;
      
      if(end1 >= n)
      {
        end1 = n - 1;
        begin2 = n;
        end2 = n-1;
      }

      if(begin2 >= n)
      {
        begin2 = n;
        end2 = n-1;
      }

      if(end2 >= n)
      {
        end2 = n-1;
      }

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
 
 
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
 
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
		}
		memcpy(a,tmp,sizeof(int)*n);
    
    rangeN *= 2;
  }  
}








